/*
 * Generator.impl.h
 *
 *  Created on: 05-06-2011
 *      Author: chfast
 */
#include <cstdlib>

namespace sudoku {

template<size_t N>
static inline symbol rand_choose(bs_t bs) {
	symbol pos = (std::rand() % N);
	while (!(bs & (1 << pos))) {
		if (pos) {
			--pos;
		} else {
			pos = N - 1;
		}
	}
	return pos;
}

template<size_t Rank>
bool Generator<Rank>::solve(Board<Rank>& board) {
	bs_t checked[Board<Rank>::nCells] = {0,};

	bool foreward = true;
	unsigned int i = 0;
	do
	{
		if (board[i].fixed) { // current cell is locked
			foreward ? ++i : --i;
			continue;
		}

		bs_t p = board.possibl(i);
		p  &= ~checked[i]; // values that can be used for current cell
		if (p == 0) {
			board[i].reset();
			checked[i] = 0;
			foreward = false;
			--i;
		} else {
			symbol r = rand_choose<Rank>(p);
			board[i] = r;
			checked[i] |= (1 << r);
			foreward = true;
			++i;
		}
	}
	while (i < board.nCells);

	return (i <= board.nCells); // if solved will be = NCells; if failed will be -1u
}

template<size_t Rank>
size_t Generator<Rank>::order(size_t x) {
	x *= 2;
	x %= Rank * Rank;
	return x;
}

template<size_t Rank>
Board<Rank> Generator<Rank>::generate(unsigned int seed) {
	srand(seed);
	Board<Rank> board;
	solve(board);
	board.save();
	board.fix();

	for (size_t i = 0; i < board.nCells; ++i) {
		size_t pos = order(i);
		bs_t ps = board.possibl(pos);
		ps ^= (1 << board[pos]);
		if (ps) {
			for (size_t j = 0; j < board.N; ++j) {
				if (ps & (1 << j)) {
					Board<9> brd_cpy(board);
					brd_cpy[pos] = j;
					if (solve(brd_cpy)) {
						goto _continue;
					}
				}
			}
		}
		board[pos].clear();
		_continue:;
	}

	return board;
}

}
